package com.atguigu.sort;

import java.util.Arrays;
import java.util.Random;

/**
 * @author 龍
 * 插入排序：将n个待排序的元素看成一个有序表和一个无序表，开始的时候有序表只含有一个元素
 * 无序表中含有n-1个元素，排序的·过程中每次从无序表中取出一个元素，将其插入到有序表的合适位置,
 * 最终正序数组即排好顺序的数组。
 * 时间复杂度为：n^2
 * 使用场景为：大部分数据已经排号顺序的时候比较好。
 * 存在的问题：当突然出现一个比较小的数的时候需要进行多次的数据后移==>shell排序
 * 花费的时间大概为：1s
 */
public class InsertSort {
    public static void main(String[] args) {
        int[] arr=new int[]{101,34,119,1};
        System.out.println(System.currentTimeMillis());
        insertSort(arr);
        System.out.println(System.currentTimeMillis());
        System.out.println(Arrays.toString(arr));
        System.out.println("-------------------------------------");
        int[] array = new int[80000];
        for (int i = 0; i < array.length; i++) {
            array[i] = new Random().nextInt(8000000);
        }
        System.out.println(Arrays.toString(array));
        System.out.println("排序前的时间：" + System.currentTimeMillis());
        insertSort(array);
        System.out.println("排序后的时间：" + System.currentTimeMillis());
        System.out.println(Arrays.toString(array));


    }
    public static void insertSort(int[] arr){
        /*使用逐步推到的方式进行
        * 第一轮{101,34,119,1}=>{34,101,119,1}
        * ，注意此数据从1开始寻找
        * */
        for (int i = 1; i < arr.length ; i++) {
            int insertVal=arr[i];
            //arr[1]的前面的这个数的坐标
            int insertIndex=i-1;
            //给indexVal找到插入的位置,保证位置的时候不出现越界。insertVal<arr[insertIndex]为升序，反过来是降序。
            while(insertIndex>=0&&insertVal<arr[insertIndex]){
                //即此时将数据后移
                arr[insertIndex+1]=arr[insertIndex];
                //将insertIndex前移
                insertIndex--;
            }
            //当退出while循环的时候，说明需要插入的位置已经找到，insertIndex+1的位置即到达了数组的最前端或者插入的值大于当前指针位置。。
            //优化：判断是否需要进行赋值,即如果当前需要插入的位置就是当值i的值，则不需要进行赋值。
            if(insertIndex+1==i){
                continue;
            }
            arr[insertIndex+1]=insertVal;
        }
    }
}
